package com.ma.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

import static com.ma.tool.system.basics.swap;

public class comparatorHeap<T> {
    private ArrayList<T> heap;
    private HashMap<T,Integer> indexHeap;
    private int heapSize;
    private Comparator<? super T> comparator;

    public comparatorHeap(Comparator<? super T> com){
        heap=new ArrayList<>();
        indexHeap=new HashMap<>();
        heapSize=0;
        comparator=com;
    }
    public boolean isEmpty(){
        return heapSize ==0;
    }

    public int size(){
        return heapSize;
    }
    
    
    
    public boolean contains(T key){
        return  indexHeap.containsKey(key);
    }
    
    public void push(T value){
        heap.add(value);
        indexHeap.put(value,heapSize);
        heapInsert(heapSize++);
    }



    public T pop(){
        T ans=heap.get(0);
        int end=heapSize-1;
        swap(0,end);
        heap.remove(end);
        indexHeap.remove(ans);
        heapify(0,--heapSize);
        return ans;
    }

    public void resign(T value){
        int valueIndex=indexHeap.get(value);
        heapInsert(valueIndex);
        heapify(valueIndex,heapSize);
    }

    private void swap(int i, int j) {
        T o1=heap.get(i);
        T o2=heap.get(j);
        heap.set(i,o2);
        heap.set(j,o1);
        indexHeap.put(o1,j);
        indexHeap.put(o2,i);


    }
    private void heapInsert(int index) {
        while (comparator.compare(
                heap.get(index),heap.get((index-1)>>1)
        )<0){
            swap(index,(index-1)>>1);
            index=(index-1)>>1;
        }


    }
    private void heapify(int index, int heapSize) {
        int left=index*2+1;//左孩子
        while (left<heapSize){
            //判断啊当前（index）节点的子节点相互比较，左节点一定存在，判断右节点是否存在且大于左节点
            int largest=(left+1)<heapSize&&(
                    comparator.compare(heap.get(left+1),heap.get(left)
                    )<0)?left+1:left;
            //判断最大的子节点是否比父节点（index）大，把大的记录下来
            largest=comparator.compare(heap.get(largest),heap.get(index))<0?largest:index;

            //如果子节点都小于父节点，则不需要下沉
            if(largest==index){
                break;
            }
            //交换大子节点与父节点
            swap(index, largest);
            //变换父节点，继续循环，继续看是否需要继续下沉
            index=largest;
            left=index*2+1;

        }



    }
}
